package Demo1;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 34255
 * Date: 2024-07-22
 * Time: 14:08
 */
public class TestHeap {
    public int[] elem;//数组
    public int useSize;//有效元素个数
    public static final int CAPACITY = 10;//容量

    public TestHeap() {//构造方法
        this.elem = new int[CAPACITY];
    }

    //初始化数组
    public void initElem(int[] array){
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
        }
        useSize = array.length;;
    }

    //向下调整
    public void shiftDown(int parent,int end){
        //找到左右节点最大值位置
        int child = 2 * parent + 1;
        while(child <= end){
            if(child + 1 <= end){//判断位置合法性
                if(elem[child] < elem[child + 1]) child++;
            }

            if(elem[parent] < elem[child]){//判断根节点是否大于最大值
                swap(child,parent);
                parent = child;
                child = child * 2 + 1;
            }else{
                break;
            }
        }
    }

    //创建大根堆
    public void createHeap(){
        //先找到最后一颗子树位置
        int index = (useSize - 1 - 1) / 2;
        for (int i = index; i >= 0; i--) {
            //交换操作
            shiftDown(i,useSize - 1);
        }
    }

    //向上调整
    public void shiftUp(int data,int child){
        int parent = (child - 1) / 2;
        while(parent >= 0){
            if(elem[child] > elem[parent]){
                swap(child,parent);
                child = parent;
                parent = (parent - 1) / 2;
            }else{
                return;
            }
        }
    }

    //添加元素
    public void offer(int data){
        //判断是否需要扩容
        if(useSize == elem.length){
            elem = Arrays.copyOf(elem,2 * elem.length);
        }

        if(useSize == 0){
            elem[useSize++] = data;
            return;
        }else{
            elem[useSize++] = data;
            shiftUp(data,useSize - 1);
        }
    }

    //检查堆是否为空
    public void checkArrayIsEmpty() throws ArrayEmptyExceptional{
        if(useSize == 0){
            throw new ArrayEmptyExceptional("堆为空");
        }
    }

    //交换值
    public void swap(int index1,int index2){
        int tmp = elem[index1];
        elem[index1] = elem[index2];
        elem[index2] = tmp;
    }

    //删除优先级最高的元素
    public int poll(){
        try{
            checkArrayIsEmpty();
            int val = elem[0];
            swap(0,useSize - 1);
            useSize--;
            //调整堆
            shiftDown(0,useSize - 1);
            return val;
        }catch(ArrayEmptyExceptional e){
            e.printStackTrace();
        }
        return -1;
    }

    //获取优先级最高的元素
    public int peek(){
        try{
            checkArrayIsEmpty();
            return elem[0];
        }catch(ArrayEmptyExceptional e){
            e.printStackTrace();
        }
        return -1;
    }

    //堆排序：有小到大
    public void heapSort(){
        int end = useSize - 1;
        while(end >= 1){
            swap(0,end);
            end--;
            shiftDown(0,end);
        }
    }

    @Override
    public String toString() {
        String str = "{";
        for (int i = 0; i < useSize; i++) {
            str = str + elem[i];
            if(i != useSize - 1) str = str + ",";
        }
        return str + "}";
    }
}
